package geek;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Tree_algorithm_day1 {

	/**
	 * Diameter of tree:
	 * The diameter of a tree(sometimes called width) is the number
	 * of nodes on the longest path between two leaves in the tree.
	 * 
	 * The diameter of a tree T is:
	 * 1) the diameter of T's left subtree
	 * 2) the diameter of T's right subtree
	 * 3) the longest path between leaves that goes through the root of T
	 *    (this can be computed from the heights of the subtrees of T)
	 *    
	 * Using dynamic programming would be better than the recursive method below
	 * while that would need to store the height of every node
	 * @param root
	 * @return
	 */
	public static <T> int findDiameterOfTree(TreeNode<T> root){
		if(root == null) return 0;

		int maxDiameter = Integer.MIN_VALUE;
		PriorityQueue<Integer> heights = new PriorityQueue<Integer>(root.children.size(), new Comparator<Integer>(){
			@Override
			public int compare(Integer o1, Integer o2) {
				if(o1 > o2) return -1;
				if(o1 < o2) return 1;
				return 0;
			}
		});
		if(root.children != null && !root.children.isEmpty()){
			for(int i = 0 ; i < root.children.size() ; i++){
				int cDiameter = findDiameterOfTree(root.children.get(i));
				if(cDiameter > maxDiameter) maxDiameter = cDiameter;
				heights.add(findHeightOfTree(root.children.get(i)));
			}
		}
		int pHeight = 1 + heights.poll() + heights.poll();
		return pHeight > maxDiameter ? pHeight : maxDiameter;
	}
	
	public static <T> int findHeightOfTree(TreeNode<T> root){
		if(root == null) return 0;
		int height = 1;
		if(root.children != null && !root.children.isEmpty()){
			PriorityQueue<Integer> heights = new PriorityQueue<Integer>(root.children.size(), new Comparator<Integer>(){
				@Override
				public int compare(Integer o1, Integer o2) {
					if(o1 > o2) return -1;
					if(o1 < o2) return 1;
					return 0;
				}
			});
			for(int i = 0 ; i < root.children.size() ; i++)
				heights.add(findHeightOfTree((TreeNode)root.children.get(i)));
			height += (int)heights.peek();
		}
		return height;
	}//*/
	
	/**
	 * 1) Get the Middle of the array and make it root.
	 * 2) Recursively do same for left half and right half.
	 * 	a) Get the middle of left half and make it left child of the root created in step 1.
	 * 	b) Get the middle of right half and make it right child of the root created in step 1.
	 * 
	 * T(n) = 2T(n/2) + C
	 * O(n)
	 * @param a
	 * @param start
	 * @param end
	 * @return
	 */
	public static <T> TreeNode constructBalancedBinarySearchTreeFromArray(T[] a, int start, int end){
		if(a == null) return null;
		if(start > end) return null;
		//if(start == end) return new TreeNode(a[start]);
		
		int val = start + (end - start)/2;
		TreeNode node = new TreeNode(a[val]);
		node.children = new ArrayList<TreeNode>();
		//if(start > -1 && val-1 < a.length && val+1 > -1){
			node.children.add(constructBalancedBinarySearchTreeFromArray(a, start, val-1));
			node.children.add(constructBalancedBinarySearchTreeFromArray(a, val+1, end));
		//}
		
		return node;
	}
	
	/**
	 * In-order traverse:
	 * Left->Root->Right for binary tree
	 * First left node -> Root -> remaining children for not binary tree
	 * @param node
	 */
	public static void inorder_traverse(TreeNode node){
		if(node == null) return;
		if(node.children != null && !node.children.isEmpty()){
			inorder_traverse((TreeNode)node.children.get(0));
		}
		System.out.print(node.val + " ");
		if(node.children != null && node.children.size() > 1){
			for(int i = 1 ; i < node.children.size() ; i++)
				inorder_traverse((TreeNode)node.children.get(i));
		}
	}
	
	/**
	 * Pre-order traverse
	 * Root->left->right
	 * @param node
	 */
	public static void preorder_traverse(TreeNode node){
		if(node == null) return;
		System.out.print(node.val + " ");
		if(node.children != null && !node.children.isEmpty())
			for(int i = 0 ; i < node.children.size(); i++)
				preorder_traverse((TreeNode)node.children.get(i));
	}
	
	/**
	 * Post-order traverse
	 * Left -> Right -> Root (children -> root)
	 * @param node
	 */
	public static void postorder_traverse(TreeNode node){
		if(node == null) return;
		if(node.children != null && !node.children.isEmpty())
			for(int i = 0 ; i < node.children.size() ; i++)
				postorder_traverse((TreeNode)node.children.get(i));
		System.out.print(node.val + " ");
	}
	
	public static <T> void bstToSortedArray(TreeNode<T> node, List<T> a){
		if(node == null) return;
		if(node.children != null && !node.children.isEmpty())
			bstToSortedArray(node.children.get(0), a);
		a.add(node.val);
		if(node.children != null && node.children.size() > 1)
			for(int i = 1 ; i < node.children.size() ; i++)
				bstToSortedArray(node.children.get(i), a);
	}
	
	/**
	 * Method 1
	 * t1 -> sorted array a1 (O(n))
	 * t2 -> sorted array a2 (O(m))
	 * t3 = sort t1 & t2 O(min(m,n))
	 * t3 -> binary array
	 * 
	 * O(m+n) with constant space
	 * 
	 * Another method is to insert it into a AVL
	 * This takes O(lg n) to insert one element
	 *
	 * @param t1
	 * @param t2
	 * @return
	 */
	public static <T> TreeNode<T> mergeTwoBalancedBinarySearchTree1(TreeNode<T> t1, TreeNode<T> t2){
		if(t1 == null || t2 == null) return null;
		List<T> a1 = new ArrayList<T>(), a2 = new ArrayList<T>();
		bstToSortedArray(t1, a1);
		bstToSortedArray(t2, a2);
		a1.addAll(a2);
		T[] a3 = (T[])a1.toArray();
		Arrays.sort(a3);
		return constructBalancedBinarySearchTreeFromArray(a3, 0, a3.length-1);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Integer[] a = new Integer[]{1,2,3,4,5,6,7,8};
		TreeNode balanceT = constructBalancedBinarySearchTreeFromArray(a, 0, 7);
		preorder_traverse(balanceT);
		System.out.println();
		inorder_traverse(balanceT);
		System.out.println();
		postorder_traverse(balanceT);
		System.out.println();
		
		System.out.println(findDiameterOfTree(balanceT));
	}

}


class TreeNode<T>{
	public T val;
	public List<TreeNode<T>> children = null;
	public TreeNode<T> parent = null;
	public TreeNode(T val){
		this.val = val;
	}
}
/**
 * the original priority queue in java  the smallest one is at the peek 
 * public int compare(Object o1, Object o2) {
				if((Integer)o1 > (Integer)o2) return -1;
				if((Integer)o1 < (Integer)o2) return 1;
				return 0;
			}
return the largest one
 */
